#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


class median_t
{
public:
    median_t(){}
    void insert(int val) {
	if (maxHeap.size() == minHeap.size()) {
	    if (minHeap.size() != 0 && minHeap.top() < val) {
		maxHeap.push(minHeap.top());
		minHeap.pop();
		minHeap.push(val);
	    } else {
		maxHeap.push(val);
	    }
	} else {
	    if (maxHeap.size() != 0 && maxHeap.top() > val) {
		minHeap.push(maxHeap.top());
		maxHeap.pop();
		maxHeap.push(val);
	    } else {
		minHeap.push(val);
	    }
	}
    }
    int getMedian() {
	if (maxHeap.size() == minHeap.size()) return (maxHeap.top()+minHeap.top())/2;
	else return maxHeap.top();
    }

private:
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int> > minHeap;
};


int main(int argc, char **argv)
{
    srand ( time(NULL) );
    median_t *ds = new median_t();

    vector<int> nums;
    for (int i = 0; i < 20; i++) {
	int num = rand()%20;
	nums.push_back(num);
	sort(nums.begin(), nums.end());
	for (int j = 0; j < nums.size(); j++)
	    cout << nums[j] << " ";
	cout << endl;
	ds->insert(num);
	cout << num << "and media is: " << ds->getMedian() << endl;
	getchar();
    }
    return 0;
}
